#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.3节：马的走法
#          0代表没有走过， 1代表走过
#  

import numpy as np
from pprint import pprint
from collections import deque

## 马走的8个方向
move = [(i, j) for i in [-1, 1] for j in [-2, 2] ] + [(i, j) for j in [-1, 1] for i in [-2, 2] ]
start_point = (1, 1)
num = 0 # 走法的总数

def seek(p, row, col, mark):
    global num, start_point
    for d in move:
        new_p = p[0] + d[0], p[1] + d[1]
        if new_p == start_point :
            num +=1
        elif 0 <= new_p[0] < row and 0 <= new_p[1] < col and not mark[new_p] :
            mark[new_p] = True
            seek(new_p, row, col, mark)
            mark[new_p] = False #回溯，恢复标记

if __name__ == '__main__':
    ROW, COL = 4, 5 # 4行 5列
    mark = np.zeros((ROW, COL), dtype=bool) #是否走过
    seek(start_point, ROW, COL, mark)
    print 'num =', num
